package lpg;

import java.util.Arrays;

class Util
{
    static int prefixMatch(char[] data, int cursor, int end, String str, String lowerCaseStr)
    {
        int length = Math.min(str.length(), end - cursor);
        for (int i = 0; i < length; i++, cursor++)
        {
            char c = data[cursor];
            if (c != str.charAt(i) && c != lowerCaseStr.charAt(i))
                return i;
        }
        return length;
    }

    static int prefixMatch(char[] data, int cursor, int end, String str)
    {
        int length = Math.min(str.length(), end - cursor);
        for (int i = 0; i < length; i++, cursor++)
        {
            if (data[cursor] != str.charAt(i))
                return i;
        }
        return length;
    }

    static boolean containsChar(String sourceString, String searchString)
    {
        for (int i = 0, n = sourceString.length(); i < n; i++)
        {
            if (searchString.indexOf(sourceString.charAt(i)) >= 0)
                return true;
        }
        return false;
    }

    //
    //  SORT sorts the elements of ARRAY and COUNT in the range LOW..HIGH
    // based on the values of the elements of COUNT. Knowing that the maximum
    // value of the elements of count cannot exceed MAX and cannot be lower
    // than zero, we can use a bucket sort technique.
    //
    static void sort(BoundedIntArray array, BoundedIntArray count, int max)
    {
        int low = array.Lbound();
        int high = array.Ubound();

        //
        // BUCKET is used to hold the roots of lists that contain the
        // elements of each bucket.  LIST is used to hold these lists.
        //
        int[] bucket = new int[max + 1];
        Arrays.fill(bucket, NIL);
        int[] list   = new int[high - low + 1];

        //
        // We now partition the elements to be sorted and place them in their
        // respective buckets.  We iterate backward over ARRAY and COUNT to
        // keep the sorting stable since elements are inserted in the buckets
        // in stack-fashion.
        //
        //   NOTE that it is known that the values of the elements of ARRAY
        // also lie in the range LOW..HIGH.
        //
        for (int i = high; i >= low; i--)
        {
            int k = count.get(i);
            int element = array.get(i);
            list[element - low] = bucket[k];
            bucket[k] = element;
        }

        //
        // Iterate over each bucket, and place elements in ARRAY and COUNT
        // in sorted order.  The iteration is done backward because we want
        // the arrays sorted in descending order.
        //
        int k = low;
        for (int i = max; i >= 0; i--)
        {
            for (int element = bucket[i]; element != NIL; element = list[element - low], k++)
            {
                array.set(k, element);
                count.set(k, i);
            }
        }
    }

    //
    //                              SORT:
    //
    //  SORT sorts the elements of ARRAY and COUNT in the range LOW..HIGH
    // based on the values of the elements of COUNT. Knowing that the maximum
    // value of the elements of count cannot exceed MAX and cannot be lower
    // than zero, we can use a bucket sort technique.
    //
    static void sort(int[] array, int[] count, int low, int high, int max)
    {
        //
        // BUCKET is used to hold the roots of lists that contain the
        // elements of each bucket.  LIST is used to hold these lists.
        //
        int[] bucket = new int[max + 1];
        Arrays.fill(bucket, NIL);
        int[] list   = new int[high - low + 1];

        //
        // We now partition the elements to be sorted and place them in their
        // respective buckets.  We iterate backward over ARRAY and COUNT to
        // keep the sorting stable since elements are inserted in the buckets
        // in stack-fashion.
        //
        //   NOTE that it is known that the values of the elements of ARRAY
        // also lie in the range LOW..HIGH.
        //
        for (int i = high; i >= low; i--)
        {
            int k = count[i];
            int element = array[i];
            list[element - low] = bucket[k];
            bucket[k] = element;
        }

        //
        // Iterate over each bucket, and place elements in ARRAY and COUNT
        // in sorted order.  The iteration is done backward because we want
        // the arrays sorted in descending order.
        //
        int k = low;
        for (int i = max; i >= 0; i--)
        {
            for (int element = bucket[i]; element != NIL; element = list[element - low], k++)
            {
                array[k] = element;
                count[k] = i;
            }
        }
    }

    static void sort(Object[] x)
    {
        // Phileas TODO: Use Dual-Pivot Quicksort?
        // http://iaroslavski.narod.ru/quicksort/
        Arrays.sort(x);
    }

    static void fillIn(StringBuilder buffer, int amount, char c)
    {
        buffer.delete(0, buffer.length());
        for (int i = 0; i < amount; i++)
            buffer.append(c);
    }

    static final int INFINITY    = Integer.MAX_VALUE;
    static final int OMEGA       = Integer.MIN_VALUE;
    static final int NIL         = Integer.MIN_VALUE + 1;

    static final String LINE_SEPARATOR;

    static
    {
        String separator = System.getProperty("line.separator");
        LINE_SEPARATOR = (separator == null) ? "\n" : separator;
    }

    private Util()
    {
    }

}
